home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 4672 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.8 KB  |  126 lines
  1. Path: mother.usf.edu!news
  2. From: yatesc@csee.usf.edu (Randy Yates)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finding a prime number
  5. Date: 6 Feb 1996 14:02:32 GMT
  6. Organization: University of South Florida
  7. Message-ID: <4f7n1o$ol9@mother.usf.edu>
  8. References: <4e875s$nqk@reader2.ix.netcom.com> <7c8_9601301722@tor250.org>
  9. NNTP-Posting-Host: ppp78.cfr.usf.edu
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.93.14
  12.  
  13. In article <7c8_9601301722@tor250.org>, Andrew.Frank@fknights.gryn.org says...
  14. >
  15. >As advtr@ix.netcom.com had made knowen to All, on 25 Jan 96  10:21:32, I
  16. >quote.
  17. > ad> From: advtr@ix.netcom.com(Advance Trading)
  18. > ad> Subject: Finding a prime number
  19. > ad> Organization: Netcom
  20. >
  21. > ad> I need to write a function that will find wether or not a number is
  22. > ad> prime.  I can come close but I get numbers that are not prime with the
  23. > ad> prime numbers.
  24. >
  25. > I recently wrote a program to do this.  It will take about 10
  26. > seconds to process a little at the start, but will then quickly tell
  27. > if any number between 4 and 4.2 billion is prime.  Here is the
  28. > source code.
  29.  
  30. Here is code that does not take a long time to start up and tests
  31. for primes in the range of unsigned long integers. The longest
  32. I've seen it run is for about 3 seconds when finding a prime
  33. around 1 billion:
  34.  
  35.  
  36.  
  37. #include<math.h>
  38. #include<stdlib.h>
  39. #include<fstream.h>
  40.  
  41. /******************************************************
  42. Programmer: R. Yates
  43. Date: 2-4-96
  44. Function: isprime 
  45.  
  46. Description:
  47.  
  48. Determines if the passed integer is prime. 
  49.  
  50. Usage:
  51.  
  52. isprime int
  53.  
  54. where int is a positive integer greater than 1.
  55. ********************************************************/
  56.  
  57. /* Command Line Usage Message */
  58. void clusage()
  59. {
  60.   cout << "ISPRIME integer\n";
  61.   cout << "  integer = a positive integer greater than 1\n";
  62. }
  63.  
  64. long gcd(long a, long b)
  65. {
  66.   long r0, r1, r2, q, r1last;
  67.  
  68.   r0 = a;
  69.   r1 = b;
  70.   r2 = 1;
  71.   while (r2 != 0)
  72.   {
  73.     r2 = r0 % r1;
  74.     r0 = r1;
  75.     r1last = r1;
  76.     r1 = r2;
  77.   }
  78.   return r1last;
  79. }
  80.  
  81. void main(int argc, char *argv[])
  82. {
  83.   long primecheck, curcheck, maxcheck;
  84.   //, firstprimes[10]={2,3,5,7,11,13,17,19,23,29};
  85.  
  86.   /* Parse the command line parameters: */
  87.   if (argc < 2)
  88.   {
  89.     clusage(); 
  90.     return;
  91.   }
  92.  
  93.   primecheck = atol(argv[1]);
  94.   if (primecheck < 2)
  95.   {
  96.     cout << "Error: integer must be greater than 1\n";
  97.     clusage();
  98.     return;
  99.   }
  100.  
  101.   curcheck=2;
  102.   maxcheck = ceil(sqrt(primecheck));
  103.   while (curcheck <= maxcheck)
  104.   {
  105.     if (gcd(primecheck, curcheck) != 1)
  106.     {
  107.       cout << "Not prime, " << curcheck << " is a divisor\n";
  108.       return;
  109.     }
  110.     curcheck++;
  111.   }
  112.   cout << "Prime\n";  
  113. }
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120. -- 
  121. % Randy Yates                  % "...the answer lies within your soul
  122. % EE/Mathematics Student       %       'cause no one knows which side 
  123. % University of South Florida  %                   the coin will fall."
  124. % <yatesc@csee.usf.edu>        %  'Big Wheels', *Out of the Blue*, ELO   
  125.  
  126.